/**
 * 二路归并排序
 */
// 归并排序
function mergeSort(arr) {
  if(arr.length <= 1) return arr
  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
  return merge(left, right)
}
// 合并
function merge(left, right) {
  const res = []
  while(left.length && right.length) {
    res.push(left[0]<right[0] ? left.shift() : right.shift())
  }
  return res.concat(left, right)
}
const arr = [1, 3, 2, 4, 5]
console.log(mergeSort(arr))